import java.util.HashMap;

public class Solution684 {
    public int[] findRedundantConnection(int[][] edges) {
        UnionUtil col= new UnionUtil();
        for (int[] tmp:edges) {
            int e_1=tmp[0];
            int e_2=tmp[1];
            int rep_1=col.find(e_1);
            int rep_2=col.find(e_2);
            if(rep_1==rep_2){
                return tmp;
            }
            col.union(e_1,e_2);
        }
        return new int[2];
    }
    private class UnionUtil{
        HashMap<Integer,Integer> Util;
        int Count;
        UnionUtil(){
            Util=new HashMap<>();
            Count=0;
        }
        int getCount(){
            return Count;
        }
        int find(int element){
            if(Util.containsKey(element)==false){
                Util.put(element,element);
                Count++;
            }
            if(Util.get(element)!=element){
                Util.put(element,find(Util.get(element)));
            }
            return Util.get(element);
        }
        void union(int x,int y){
            int rootx=find(x);
            int rooty=find(y);
            if(rootx==rooty){
                return;
            }
            Util.put(rootx,rooty);
            Count--;

        }
    }
}
